#include "DoubleLinkList.h"
#include <iostream>

DoubleLinkList::DoubleLinkList():size(0)
{
    // head = new Node(0);
    // tail = head;
    head = tail = new Node(0);
}

void DoubleLinkList::InsertTail(const ElementType &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

void DoubleLinkList::InsertHead(const ElementType &element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    newNode->prev = head;
    head->next = newNode;
    if(size != 0)
    {
        newNode->next->prev = newNode;
    }
    else
    {
        tail = newNode;
    }
    size++;
}

void DoubleLinkList::InsertByIndex(int index, const ElementType &element)
{
    if(index < 0 || index > size)
    {
        return;
    }
    Node *travelPoint = head;
    for(int i = 0; i < index; i++) 
    {
        travelPoint = travelPoint->next;
    }

    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;
    travelPoint->next = newNode;
    if (newNode->next != nullptr)
    {
        newNode->next->prev = newNode;
    }
    else
        tail = newNode;
    size++;
}

void DoubleLinkList::RemoveByIndex(int index)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    Node *travelPoint = head;
    for(int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    if(freeNode == tail)
    {
        tail = tail->prev;
    }
    else
    {
        freeNode->next->prev = travelPoint;
    }
    delete freeNode;
    size--;
}

void DoubleLinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            if(freeNode == tail)
            {
                tail = tail->prev;
            }
            else
            {
                freeNode->next->prev = travelPoint;
            }
            delete freeNode;
            size--;
        }
        else 
        {
            travelPoint = travelPoint->next;
        }
    }
}

void DoubleLinkList::UpDateByElement(const ElementType &Oldelement,const ElementType &Newelement)
{
    Node * travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == Oldelement)
        {
            travelPoint->value = Newelement;
        }
        travelPoint = travelPoint->next;
    }
}



size_t DoubleLinkList::FindByElement(const ElementType &element)
{
    size_t result = 0;
    Node * travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value != element)
        {
            travelPoint = travelPoint->next;
            result++;
        }
        else
            break;
    }
    return result;
}

// void DoubleLinkList::Sort()
// {
//     FastSort(head->next,tail);
// }

// void DoubleLinkList::FastSort( Node *head,Node *tail)
// {
//     if(head <= tail )
//     {
//         return;
//     }
//     int temp  = head->next->value; 
//     Node *start = head->next;
//     Node *end = tail;
//     while(start != end)
//     {
//         while(end->value > temp && start != end)
//         {
//             end = end->prev;
//         }
//         if(start != end)
//         {
//             start->next->value = end->value;
//         }

//          while(start->value < temp && start != end)
//         {
//             start = start->next;
//         }
//         if(start != end)
//         {
//             end->prev->value = start->next->value; 
//         }
//     }
//     start->value = temp;
//     FastSort(head->prev,start);
//     FastSort(end->next,tail);
// }

DoubleLinkList DoubleLinkList::Merge(const DoubleLinkList & list)
{
    DoubleLinkList result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    while(p1 && p2)
    {
        if(p1->value < p2->value)
        {
            result.InsertTail(p1->value);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
    }
    while(p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while(p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }
    return result;
}

// DoubleLinkList DoubleLinkList::Merge(const DoubleLinkList & list)
// {
//     DoubleLinkList result;
//     Node *p1 = tail;
//     Node *p2 = list.tail;
//     while(p1->prev != head && p2->prev != head)
//     {
//         if(p1->value < p2->value)
//         {
//             result.InsertTail(p2->value);
//             p2 = p2->prev;
//         }
//         else if(p1->value > p2->value)
//         {
//             result.InsertTail(p1->value);
//             p1 = p1->prev;
//         }
//         else
//         {
//             result.InsertTail(p2->value);
//             result.InsertTail(p1->value);
//             p2 = p2->prev;
//             p1 = p1->prev;
//         }
//     }
//     while(p1 && p1->prev != nullptr)
//     {
//         result.InsertTail(p1->value);
//         p1 = p1->prev;
//     }
//     while(p2 && p2->prev != nullptr)
//     {
//         result.InsertTail(p2->value);
//         p2 = p2->prev;
//     }
//     return result;
// }

size_t DoubleLinkList::Size()
{
    return size;
}


void DoubleLinkList::show()
{
    std::cout<<"size : "<<size<<std::endl;
    Node *travelPoint = head->next; //存放有效数据的第一个节点
    while(travelPoint != nullptr) //当前节点存在
    {
        std::cout<<travelPoint->value<<" "; //当前指针不为空
        travelPoint = travelPoint->next; //访问下一个节点
    }
    std::cout<<std::endl;
}

void DoubleLinkList::ReserveShow()
{
    std::cout<<"size : "<<size<<std::endl;
    Node *travelPoint = tail; 
    while(travelPoint != head) //排除头节点
    {
        std::cout<<travelPoint->value<<" "; 
        travelPoint = travelPoint->prev; 
    }
    std::cout<<std::endl;
}

ElementType &DoubleLinkList::operator[](int index)
{
    Node *travelPoint = head;
    for(int i = 0;i <= index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return travelPoint->value;
}
